#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0033.py
@time: 2021/11/10 16:37
@desc: https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
'''


class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.num_list = []

    def addNum(self, num: int) -> None:
        if len(self.num_list) == 0:
            self.num_list.append(num)
        else:
            if num>self.num_list[-1]:
                self.num_list.append(num)
            for i in range(len(self.num_list)):
                if self.num_list[i] > num:
                    self.num_list.insert(i, num)
                    break

    def findMedian(self) -> float:
        n = len(self.num_list)
        if n == 0:
            return None
        if n % 2 == 0:
            return (self.num_list[n // 2] + self.num_list[n // 2 - 1]) / 2
        else:
            return self.num_list[n // 2]


if __name__ == '__main__':
    inp_str = ["MedianFinder","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian"]
    inp_num = [[],[12],[],[10],[],[13],[],[11],[],[5],[],[15],[],[1],[],[11],[],[6],[],[17],[],[14],[],[8],[],[17],[],[6],[],[4],[],[16],[],[8],[],[10],[],[2],[],[12],[],[0],[]]
    exp = [None,None,12.0,None,11.0,None,12.0,None,11.5,None,11.0,None,11.5,None,11.0,None,11.0,None,11.0,None,11.0,None,11.0,None,11.0,None,11.0,None,11.0,None,11.0,None,11.0,None,11.0,None,10.5,None,10.0,None,10.5,None,10.0]
    # inp_str = ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
    # inp_num = [[], [1], [2], [], [3], []]
    output = []
    for str, num, e in zip(inp_str, inp_num, exp):
        if str == 'MedianFinder':
            m = MedianFinder()
            output.append(None)
        elif str == 'addNum':
            m.addNum(num[0])
            output.append(None)
        elif str == 'findMedian':
            me = m.findMedian()
            if not me==e:
                print(m.num_list)
            output.append(me)
    
    print(output)

